vlabwikiaorg_ru-20200214-history
Оптимизация (информатика)
Это статья об оптимизации программ и данных на всех этапах программирования. : Об оптимизациях, применяемых компиляторами, см.: Оптимизация компилятора. В информатике оптимизацией называется процесс модификации системы для улучшения её эффективности. Система может быть одиночной компьютерной программой, набором компьютеров или даже целой сетью, такой как Internet. Несмотря на то, что слово «оптимизация» использует тот же самый корень, что и слово «оптимальный», процесс оптимизации весьма редко порождает оптимальную систему, поэтому всегда имеются уступки (tradeoffs). Оптимизация должна проводиться с осторожностью. Тони Хоар впервые произнёс, а Дональд Кнут впоследствии часто повторял известное высказывание: «Преждевременная оптимизация — это корень всех бед». Очень важно иметь для начала озвученный алгоритм и работающий прототип. Основы Некоторые задачи часто могут быть выполнены более эффективно. Например, рассмотрим следующую программу на языке Си, которая суммирует все целые числа от 1 до N: int i, sum = 0; for (i = 1; i <= N; i++) sum += i; printf ("sum: %d\n", sum); Этот код может быть (подразумевая, что нет переполнения) переписан, используя математическую формулу, в следующем виде: int sum = (N * (N+1)) / 2; printf ("sum: %d\n", sum); Термин «оптимизация» обычно подразумевает, что система сохраняет ту же самую функциональность. Однако, значительное улучшение производительности часто может быть достигнуто с помощью решения насущной проблемы и удаления избыточной функциональности. Например, если обоснованно допустить, что программе не требуется поддерживать более, чем (скажем) 100 элементов при вводе, то возможно использовать статическое выделение памяти вместо медленного динамического. Уступки (tradeoffs) Оптимизация в основном фокусируется на одиночном или повторном времени выполнения, использовании памяти, дискового пространства, пропускной способности или некотором другом ресурсе. Это обычно требует уступок — один параметр оптимизируется за счёт других. Например, увеличение размера кэша улучшает производительность времени выполнения, но также увеличивает потребление памяти. Другие распространённые уступки включают прозрачность кода и его выразительность. Сложные специализированные алгоритмы требуют больше усилий по отладке и увеличивают вероятность ошибок. Различные области В исследовании операций, оптимизация — это проблема определения входных значений функции, при которых она имеет максимальное или минимальное значение. Иногда на эти значения накладываются ограничения, такая задача известна как ограниченная оптимизация. В программировании, оптимизация обычно обозначает модификацию кода и его установок компиляции для данной архитектуры для производства более эффективного ПО. Типичные проблемы имеют настолько большое количество возможностей, что программисты обычно могут позволить использовать только «достаточно хорошее» решение. Узкие места Для оптимизации требуется найти узкое место: критическую часть кода, которая является основным потребителем необходимого ресурса. Улучшение примерно 20 % кода влечёт за собой изменение 80 % результатов (см. также принцип Парето). Архитектурный дизайн системы особенно сильно влияет на её производительность. Выбор алгоритма влияет на эффективность больше, чем любой другой элемент дизайна. Более сложные алгоритмы и структуры данные могут хорошо оперировать с большим количеством элементов, в то время как простые алгоритмы подходят для небольших объёмов данных — накладные расходы на инициализацию более сложного алгоритма могут перевесить выгоду от его использования. Чем больше памяти использует программа, тем быстрее она обычно выполняется. Например, программа-фильтр обычно читает каждую строку, фильтрует и выводит эту строку непосредственно. Поэтому она использует память только для хранения одной строки, но её производительность обычно очень плохая. Производительность может быть значительно улучшена чтением целого файла и записью потом отфильтрованного результата, однако этот метод использует больше памяти. Кэширование результата также эффективно, однако требует большего количества памяти для использования. Простейшие приёмы оптимизации программ по затратам процессорного времени Оптимизация по затратам процессорного времени особенно важна для расчетных программ, в которых большой удельный вес имеют математические вычисления. Здесь перечислены некоторые приемы оптимизации, которые может использовать программист при написании исходного текста программы. Инициализация объектов данных Во многих программах какую-то часть объектов данных необходимо инициализировать, то есть присвоить им начальные значения. Такое присваивание выполняется либо в самом начале программы, либо, например, в конце цикла. Правильная инициализация объектов позволяет сэкономить драгоценное процессорное время. Так, например, если речь идет об инициализации массивов, использование цикла, скорее всего, будет менее эффективным, чем объявление этого массива прямым присвоением. Программирование арифметических операций В том случае когда значительная часть времени работы программы отводится арифметическим вычислениям, немалые резервы повышения скорости работы программы таятся в правильном программировании арифметических (и логических) выражений. Важно понимать, что различные арифметические операции значительно различаются по быстродействию. Самыми быстрыми являются операции сложения и вычитания. Более медленным является умножение, затем идет деление. Относительно много времени тратится на обращение к подпрограммам. Быстродействие также зависит и от типа операндов. Например, в языке Turbo Pascal ввиду особенностей реализации целочисленной арифметики операция сложения оказывается наиболее медленной для операндов типа Byte и ShortInt (несмотря на то, что переменные занимают один байт, арифметические операции для них - двухбайтовые. При выполнении операций над типами Byte и ShortInt производится обнуление старшего байта регистров, второй операнд копируется из памяти в регистр. Это и приводит к дополнительным затратам времени). Программируя арифметические выражения, следует выбирать такую форму их записи, чтобы количество "медленных" операций было сведено к минимуму. Рассмотрим такой пример. Пусть необходимо вычислить многочлен 4-й степени: : ax^4+bx^3+cx^2+dx+e При условии, что вычисление степени производится перемножением основания определенное число раз, нетрудно найти, что в этом выражении содержится 10 умножений ("медленных" операций) и 4 сложения ("быстрых" операций). Это же самое выражение можно записать в виде: : (((ax+b)x+c)x+d)x+e Такая форма записи называется схемой Горнера. В этом выражении 4 умножения и 4 сложения. Общее количество операций сократилось почти в два раза, соответственно уменьшится и время вычисления многочлена. Циклы Различается и время выполнения циклов разного типа. Время выполнения цикла со счетчиком и цикла с постусловием при всех прочих равных условиях совпадает, цикл с предусловием выполняется несколько дольше (примерно на 20-30 %). При использовании вложенных циклов следует иметь в виду, что затраты процессорного времени на обработку такой конструкции могут зависеть от порядка следования вложенных циклов. Рассмотрим, например, такой вложенный цикл со счетчиком на языке Turbo Pascal: for j := 1 to 100000 do for k := 1 to 1000 do a := 1; Этот цикл выполняется примерно на 10 % дольше, чем следующий: for j := 1 to 1000 do for k := 1 to 100000 do a := 1; На первый взгляд, и в первом и во втором случае 10 000 000 раз выполняется оператор присваивания, и затраты времени на это должны быть одинаковы в обеих случаях. Но это не так. Объясняется наше наблюдение тем, что инициализации цикла, то есть обработка процессором его заголовка с целью определения начального и конечного значений счетчика, а также шага приращения счетчика требует времени. В первом случае 1 раз инициализируется внешний цикл и 100 000 раз - внутренний, то есть всего выполняется 100 001 инициализация. Во втором случае, как нетрудно подсчитать, таких инициализаций оказывается всего лишь 1001. Аналогично ведут себя вложенные циклы с предусловием и с постусловием. Можно сделать вывод, что при программировании вложенных циклов по возможности следует делать цикл с наибольшим числом повторений самым внутренним, а цикл с наименьшим числом повторений - самым внешним. При вычислении сумм часто используются циклы, содержащие одинаковые операции, относящиеся к каждому слагаемому. Это может быть, например, общий множитель (язык Turbo Pascal): summa := 0; for i := 1 to 1000 do summa := summa + a * xi; Очевидно, что другая форма записи этого цикла оказывается более экономной: summa := 0; for i := 1 to 1000 do summa := summa + xi; summa := a * summa; Инвариантные фрагменты кода Тема оптимизации инвариантных фрагментов кода тесно связана с проблемой оптимального программирования циклов. Внутри цикла могут встречаться выражения, фрагменты которых никак не зависят от управляющей переменной цикла. Их называют инвариантными фрагментами кода. Современные компиляторы часто определяют наличие таких фрагментов и выполняют их автоматическую оптимизацию. Такое возможно не всегда, и иногда производительность программы зависит целиком от того, как запрограммирован цикл. В качестве примера рассмотрим следующий фрагмент программы (язык Turbo Pascal): for i := 1 to n do begin ... for k := 1 to p do for m := 1 to q do begin am := Sqrt(x * k * m - i) + Abs(u * i - x * m + k); bm := Sin(x * k * i) + Abs(u * i * m + k); end; ... am := 0; bm := 0; for k := 1 to p do for m := 1 to q do begin am := am + am / ck; bm := bm + bm / ck; end; end; Здесь инвариантными фрагментами кода являются слагаемое Sin(x * k * i) в первом цикле по переменной m''' и операция деления на элемент массива '''ck во втором цикле по m'''. Значения синуса и элемента массива не изменяются в цикле по переменной '''m, следовательно, в первом случае можно вычислить значение синуса и присвоить его вспомогательной переменной, которая будет использоваться в выражении, находящемся внутри цикла. Во втором случае можно выполнить деление после завершения цикла по m. Таким образом можно существенно сократить количество трудоемких арифметических операций. См. также * Оптимизация в Java * Оптимизация в C++ * Абстрактная интерпретация * Метрика хорошести * Кэширование * Принцип KISS * Граф передачи управления * Ленивые вычисления * Низкоуровневая виртуальная машина * Мемоизация * Окрестность памяти * Профилирование (анализ производительности) * Теория очередей * Симулятор * Гипотетическое исполнение * Время выполнения наихудшего случая Ссылки * Programming Optimization * C, C++ optimization * C optimization tutorial * Software Optimization at Link-time And Run-time * Profiling and optimizing Ruby code * Никлаус Вирт. A Plea for Lean Software * Description from the Portland Pattern Repository * Улучшаем производительность приложения путём перераспределения кода * ПОИСК ГЛОБАЛЬНОГО ОПТИМУМА * Оптимизация 64-битных программ Литература * Jon Bentley. Writing Efficient Programs. ISBN 0-13-970251-2 * * * * Категория:Оптимизация Категория:Разработка программного обеспечения